package com.exercises;

import com.alibaba.fastjson.JSONArray;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Exercise785 {
    public static void main(String[] args) {
        String string = "[[1,3],[0,2],[1,3],[0,2]]";

        JSONArray jsonArray = JSONArray.parseArray(string);
        int[][] arr = new int[jsonArray.size()][];
        for (int i = 0; i < jsonArray.size(); i++) {
            JSONArray jsonArray2 = jsonArray.getJSONArray(i);
            int[] arr2 = new int[jsonArray2.size()];
            for (int j = 0; j < jsonArray2.size(); j++) {
                arr2[j] = jsonArray2.getIntValue(j);

            }
            arr[i] = arr2;
        }
        System.out.println(new Exercise785().isBipartite(arr));


    }

    public boolean isBipartite(int[][] graph) {
        Integer[] colors = new Integer[graph.length];
        int[] undo = new int[graph.length];


        Queue<Integer> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < graph.length; i++) {
            if (graph[i].length > 0 && !list.contains(i)) {
                list.add(i);
            }
        }
        while (list.size() > 0) {
            int idx = list.remove(0);
            if (undo[idx] == 1) {
                continue;
            }
            colors[idx] = 0;
            queue.add(idx);
            while (!queue.isEmpty()) {
                Integer index = queue.remove();
                undo[index] = 1;
//                System.out.println(index);
                Integer color = colors[index];
                int[] value = graph[index];
                for (int v : value) {
                    if (colors[v] == null) {
                        colors[v] = 1 - color;
                    } else if (colors[v] == color) {
                        return false;
                    }
                    if (undo[v] == 0) {
                        queue.add(v);
                    }
                }

            }
        }
        return true;
    }
}

